# 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位
# 。 
# 
#  返回 滑动窗口中的最大值 。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
# 输出：[3,3,5,5,6,7]
# 解释：
# 滑动窗口的位置                最大值
# ---------------               -----
# [1  3  -1] -3  5  3  6  7       3
#  1 [3  -1  -3] 5  3  6  7       3
#  1  3 [-1  -3  5] 3  6  7       5
#  1  3  -1 [-3  5  3] 6  7       5
#  1  3  -1  -3 [5  3  6] 7       6
#  1  3  -1  -3  5 [3  6  7]      7
#  
# 
#  示例 2： 
# 
#  
# 输入：nums = [1], k = 1
# 输出：[1]
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= nums.length <= 10⁵ 
#  -10⁴ <= nums[i] <= 10⁴ 
#  1 <= k <= nums.length 
#  
# 
#  Related Topics 队列 数组 滑动窗口 单调队列 堆（优先队列） 👍 3014 👎 0
from collections import deque
from typing import List
from sortedcontainers import SortedList
import heapq


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """
        平衡二叉搜索树:插入,删除,查找最大值的时间复杂度均为nlogn,使用此方法时间复杂度较高
        :param nums:
        :param k:
        :return:

        res = []
        sorted_list = SortedList()
        s, e, n = 0, k-1, len(nums)
        while e < n:
            if len(sorted_list) == 0:
                for i in range(0, k):
                    sorted_list.add(nums[i])
            else:
                # 加一个删一个
                sorted_list.remove(nums[s - 1])
                sorted_list.add(nums[e])

            res.append(sorted_list[-1])
            s += 1
            e += 1
        return res
        """
        """
        思路二:最大堆
        """

        # 值取符号即把可把最小堆变为最大堆(堆比较元组的一个元素),另外加入索引是为了后面比较新加入的元素是否在窗口中
        q = [(-nums[i], i) for i in range(k)]
        # 构建最小堆,最小堆顶部为最小的,因为是存入的负数,顶部的即为最大值,堆查找最值为o(1),构建堆为o(n)
        heapq.heapify(q)
        res = [-q[0][0]]
        n = len(nums)
        for i in range(k, n):
            # 加入新值
            heapq.heappush(q, (-nums[i], i))
            # 若堆顶的元素不在窗口中,则删去堆顶元素
            while q[0][1] <= i - k:
                heapq.heappop(q)

            res.append(-q[0][0])

        return res


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().maxSlidingWindow(nums=[1, 3, -1, -3, 5, 3, 6, 7], k=3))
